package _220317;


import java.io.*;

/**
 * @author ShadowLim
 * @create 2022-03-17-17:37
 */
public class _数的幂次 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer IN = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) throws IOException {
        /**
         * nextInt()方法求 t ：可以直接替换为以下代码
         *  IN.nextToken();
         *  int t = (int)IN.nval;
         */
        int t = nextInt();
        while (t-- > 0) {
            long n = nextInt();
            long m = nextInt();
            long p = nextInt();
            out.write(check(n, m, p) + "\n");
        }
        out.flush();
    }

    private static int nextInt() throws IOException {
        IN.nextToken();
        return (int)IN.nval;
    }

    private static long check(long n, long m, long p) {
        long res = 1;
        // 快速幂取模 求解(n ^ m) % p = (n % p) ^ m % p
        while (m > 0) {
            if ((m & 1) == 1) {
                res = (res * n) % p;  // * 的优先级更高 括号可以不加
            }
            m >>= 1;
            n = (n * n) % p;    // 括号可以不加
        }
        return res;
    }
}
